1. Field of the Invention
The present invention relates generally to computer implemented graphics applications, and in particular, to a method, apparatus, and article of manufacture for sorting lines displayed in a computer graphics application.
2. Description of the Related Art
Computer-implemented graphics (CAD) systems have been widely used by designers, illustrators, drafters, and engineers for a number of years. In such graphics systems, objects such as points, lines, and shapes are displayed in a drawing. Commonly, objects may overlap or intersect with each other. When one object is placed over or on top of another object, the objects are referred to as coincident.
When objects are coincident, some CAD systems may graphically display only one object. For example, if two points are coincident, only one of the points needs to be displayed. In another example, some CAD programs automatically generate centerlines or cylindrical features for an object (e.g., for holes, circular extrusions, etc.). Such centerlines may be graphically represented by dashed lines. Further, if one centerline is coincident with another centerline (e.g., if one hole is directly in front of another), the two dashed lines may appear to merge into a single solid line.
To display coincident objects as one object (e.g., as a solid line), the CAD program must determine when objects are coincident. Sorting algorithms/techniques have been used to determine when points are adjacent or near each other. For example, a quadtree algorithm is used to rapidly sort points in two dimensions. Similarly, an octtree can be used to rapidly sort points in three dimensions.
The quadtree algorithm can begin with a square or other shape equivalent to a bounding box for the shape (a bounding box is the smallest box that can contain the two or three dimensional object) in an area or plane (referred to as the root of the quadtree). Conceptually, the large square can be broken into four smaller squares (or bounding boxes) of half the perimeter and a quarter the area each. The four smaller squares are the four children of the root. Each child can in turn be broken into four (4) subsquares to get its children and so on. Each box is represented in a tree structure as a node, with four branches from each node connecting the node to its children. The smallest boxes are represented as leaves at the bottom of the tree. Each leave of the quadtree is stored in memory. An octtree is similar, but with eight (8) children per node, corresponding to the eight (8) subcubes of a larger cube.
The quadtree and octtree are constructed to store points with the leaves of the tree containing (or having pointers to) the positions of the points (and other information) in the corresponding box. If points are not uniformly distributed on a drawing/bounding box, many of the leaves of a quadtree are empty. Accordingly, in a quadtree, instead of storing the empty leaves, the squares may be subdivided only when they contain more than one (1) point. Consequently, there may be exactly as many leaves as points (or several points on a leaf) and the children may be ordered counterclockwise starting at the lower left. FIG. 1A illustrates a drawing that has been subdivided in accordance with the adaptive quadtree algorithm. FIG. 1B illustrates an adaptive quadtree in accordance with the drawing of FIG. 1A.
Although the quadtree algorithm is utilized to sort points in two (2) dimensions, there are currently no mechanisms available to determine when two lines or objects are coincident. To make such a determination, every object/line in a drawing is compared to every other line in the drawing. Such a comparison results in operations on the order of the square of the number of lines, which can be prohibitive for a large number of lines. Thus, there is a need in the art for a fast and efficient method for sorting lines and determining when lines are coincident.
A method, system, apparatus, and article of manufacture for determining coincident lines. Graphics application programs often need to determine when two or more lines are coincident. One or more embodiments of the invention obtain dual points by examining the intersection between each line and a perpendicular projection from the line to a point of origin. An angular tolerance and a parallel distance tolerance are obtained to utilize in the determination of a tolerance value for coincident lines.
The dual points are sorted in accordance with a modified quadtree algorithm or octtree. The drawing is recursively broken up into equal subdivisions (e.g., four quadrants if two dimensional or eight if three dimensional) until the maximum allowed number of points for a subdivision has been reached or until the size of the subdivision is less than a tolerance value. Once the number of points in a subdivision is less than or equal to the maximum allowed number of points per subdivision, the points can be individually compared to each other. Further, if the subdivision is less than a tolerance value, the subdivision is small enough such that all of the lines within the subdivision are coincident. If the number of points is greater than the maximum allowed number of points and the subdivision is larger than the tolerance, the area is recursively subdivided.
If two or more dual points are in a subdivision, to determine if the lines represented are coincident, a tolerance value is compared to the distance between the two dual points. If the distance is less than (or equal to) the tolerance value, the lines are coincident. If the distance is greater than the tolerance value, the lines are not coincident. The tolerance value that is utilized in the comparison may be obtained by multiplying an angular tolerance by the distance from the point of origin to the center of the subdivision. Alternatively, if lines are parallel, a parallel distance tolerance may be utilized in the comparison.